package algorithms.sort;

import java.util.Arrays;

/**
 * 计数排序,使用在数据在一点范围（较小）的数据。
 *  如arr中存放员工的年龄，请堆arr进行排序
 *  思路：申请一个额外数组countArr[200]（词频表）存放该年龄的人数。
 *       1.先跑一遍arr数组统计每个年龄的人数；
 *       2.根据词频表给原数组赋值，完成排序。
 *  时间复杂度：O(N)
 *  空间复杂度：O(1)
 */
public class CountSort {
    public static void main(String[] args) {
        int[] arr = GetRandomArr.getRandomArr100(11);
        countSort(arr,100);
        System.out.println(Arrays.toString(arr));
        //System.out.println(Arrays.toString(countArr));
    }

    /**
     * 计数排序
     *
     * @param arr : 数组
     * @param range ：数组的值的范围 [0-range]-->词频数组的大小
     */
    public static void countSort(int[] arr,int range) {
        if(arr == null || arr.length <=1)
            return;
        int[] countArr = new int[range + 1];
        //  1.先跑一遍arr数组统计每个年龄的人数；
        for (int e : arr) {
            countArr[e] = countArr[e] + 1;
        }
        // 2.根据词频表给原数组赋值，完成排序。
        int index = 0;
        for (int i = 0;i<countArr.length;i++) {
            for(int j = 0;countArr[i] > 0 && j < countArr[i];j++) {
                arr[index++] = i;
            }
        }
    }
}
